﻿// 601 逆序对2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
http://oj.daimayuan.top/course/22/problem/653


有 n个数 a1,a2,…,an
，对于其中的两个数字 x,y，如果满足 x出现的位置在 y出现的位置前面并且 x比 y大，
 则称 (x,y)为数组 a的一个逆序对。请问数组 a的逆序对一共有多少个？形式化的说，请求出有多少组 (i,j)满足 i<j并且 ai>aj。

输入格式
第一行一个整数 n。

接下来一行 n个整数，a1,a2,…,an。

输出格式
一行一个数，表示答案。

样例输入
4
4 2 3 1
样例输出
5
样例解释
5 个逆序对分别为 (4,2),(4,3),(4,1),(2,1),(3,1)。

数据范围
对于 100%的数据，保证 2≤n≤100000,1≤ai≤n并且每个数字都只会出现一次。
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

int a[N], tmp[N];

LL merge_sort(int q[], int l, int r)
{
    if (l >= r) return 0;

    int mid = l + r >> 1;

    LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else
        {
            res += mid - i + 1;
            tmp[k++] = q[j++];
        }
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];

    for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];

    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    cout << merge_sort(a, 0, n - 1) << endl;

    return 0;
}